// 全排列：不限次数版
// 输入一个数组，要求返回数组中的n个元素，该方法会返回所有的排列
// 比如数组[1,2,3,4],要求返回4个元素的集合。那在此逻辑中，可以返回[1,1,1,1]，即数组中的元素不限使用次数
// 这个很适合与计算+-*/四则运算，要求获取多少种计算公式
/**
 *
 * @param {*} arr 输入数组
 * @param {*} max 包含max个元素的所有数组排列
 * @returns
 */
function ArrangementInfinite(arr, max) {
    // 后面实现全排列的逻辑，是按照树的生成方式来实现的。
    // 想象有N棵树，每棵树的根节点是其元素i，i的每种排列方式是从根节点到叶节点的一个唯一的组合
    // 那所有N棵树再加上所有的组合即为全排列

    arr.sort((a, b) => a - b);

    let count = arrangementCount(arr, max);
    console.log(`input: ${JSON.stringify(arr)}, max: ${max}`);
    console.log(`arrangementCount: ${count}`);

    let ret = []; // 用于存储所有的组合方式，一种组合记录一个

    for (let i = 0; i < arr.length; i++) {
        dfs(arr, max, i, 0, [], ret);
    }

    return ret;
}

function arrangementCount(arr, max) {
    return arr.length ** max;
}

/**
 * 返回数组arr的全排列
 * @param {*} arr 当前可用数组成的数组，排列每经过一层，都会失去一个元素
 * @param {*} max 递归总层数
 * @param {*} index 根节点index
 * @param {*} level 递归当前所处的层数
 * @param {*} acc 当前排列的数组
 * @param {*} allArrangement 存储所有的组合方式，一种组合记录一个
 * @returns
 */
function dfs(arr, max, index, level, acc, allArrangement) {
    let newAcc = JSON.parse(JSON.stringify(acc));
    newAcc.push(arr[index]);

    if (newAcc.length === max || level === max) {
        allArrangement.push(newAcc);
        return;
    }

    for (let i = 0; i < arr.length; i++) {
        dfs(arr, max, i, level + 1, newAcc, allArrangement);
    }
}

module.exports = {
    ArrangementInfinite,
};

// var ret = ArrangementInfinite(['+', '-', '*', '/'], 3);
// console.table(ret);
